《每日一道面试题》 第三期

查看原文

其他

《每日一道面试题》第三期

Original: 陈宇明码个蛋 2019-06-22

码个蛋(codeegg)第 634 次推文

码仔，今天就给大家带来了《每日一道面试题》的第三期：

设计模式的基本原则

单一职责原则(Single Responsibility Principle)
单一职责原则表示一个模块的组成元素之间的功能相关性。从软件变化的角度来看，就一个类而言，应该仅有一个让它变化的原因；通俗地说，即一个类只负责一项职责。

SRP 是一个简单又直观的原则，但是在实际编码的过程中很难将它恰当地运用，需要结合实际情况进行运用。
单一职责原则可以降低类的复杂度，一个类仅负责一项职责，其逻辑肯定要比负责多项职责简单。
提高了代码的可读性，提高系统的可维护性。

开放-关闭原则(Open-Closed Principle)

开放-关闭原则表示软件实体 (类、模块、函数等等) 应该是可以被扩展的，但是不可被修改。

如果一个软件能够满足 OCP 原则，那么它将有两项优点：

能够扩展已存在的系统，能够提供新的功能满足新的需求，因此该软件有着很强的适应性和灵活性。
已存在的模块，特别是那些重要的抽象模块，不需要被修改，那么该软件就有很强的稳定性和持久性。

里氏替换原则(Liskov Substitution Principle)

将一个基类对象替换成它的子类对象，程序将不会产生任何错误和异常，反过来则不成立，如果一个软件实体使用的是一个子类对象的话，那么它不一定能够使用基类对象。即子类可以扩展父类的功能，但不能改变父类原有的功能

依赖倒转原则(Dependence Inversion Principle)

高层模块不应该依赖低层模块，二者都应该于抽象。进一步说，抽象不应该依赖于细节，细节应该依赖于抽象。遵循依赖倒转原则可以降低类之间的耦合性，提高系统的稳定性，降低修改程序造成的风险。依赖倒转原则的核心就是要我们面向接口编程

接口隔离原则(Interface Segregation Principle)

客户端不应该依赖它不需要的接口；一个类对另一个类的依赖应该建立在最小的接口上

接口隔离原则的思想在于建立单一接口，尽可能地去细化接口，接口中的方法尽可能少
但是凡事都要有个度，如果接口设计过小，则会造成接口数量过多，使设计复杂化。所以一定要适度

迪米特法则(Law Of Demeter)

迪米特法则又称为最少知道原则，它表示一个对象应该对其它对象保持最少的了解。通俗来说就是，只与直接的朋友通信。

直接的朋友：每个对象都会与其他对象有耦合关系，只要两个对象之间有耦合关系，我们就说这两个对象之间是朋友关系。耦合的方式很多，依赖、关联、组合、聚合等。其中，我们称出现成员变量、方法参数、方法返回值中的类为直接的朋友，而出现在局部变量中的类则不是直接的朋友。也就是说，陌生的类最好不要作为局部变量的形式出现在类的内部。

对于被依赖的类来说，无论逻辑多么复杂，都尽量的将逻辑封装在类的内部，对外提供 public 方法，不对泄漏任何信息。

组合/聚合复用原则(Composite/Aggregate Reuse Principle)

组合/聚合复用原则就是在一个新的对象里面使用一些已有的对象，使之成为新对象的一部分; 新的对象通过向这些对象的委派达到复用已有功能的目的。

在面向对象的设计中，如果直接继承基类，会破坏封装，因为继承将基类的实现细节暴露给子类；如果基类的实现发生了改变，则子类的实现也不得不改变；从基类继承而来的实现是静态的，不可能在运行时发生改变，没有足够的灵活性。于是就提出了组合/聚合复用原则，也就是在实际开发设计中，尽量使用组合/聚合，不要使用类继承。

总体说来，组合/聚合复用原则告诉我们：组合或者聚合好过于继承
聚合组合是一种 “黑箱” 复用，因为细节对象的内容对客户端来说是不可见的

谈谈Java中多线程实现的几种方式

Java中多线程实现的方式主要有三种：

继承Thread类
实现Runnable接口
使用ExecutorService、Callable、Future实现有返回结果的多线程

其中前两种方式线程执行完没有返回值，只有最后一种是带返回值的。

继承Thread类实现多线程：

继承Thread类本质上也是实现Tunnable接口的一个实例，他代表一个线程的实例，并且启动线程的唯一方法是通过Thread类的start（）方法，start（）方法是一个native方法，他将启动一个新线程，并执行run( )方法。

实现Runnable接口方式实现多线程：

实例化一个Thread对象，并传入实现的Runnable接口，当传入一个Runnable target参数给Thread后，Thraed的run（）方法就会调用target.run( );

使用ExecutorService、Callable、Future实现有返回结果的多线程：

可返回值的任务必须实现Callable接口，类似的无返回值的任务必须实现Runnable接口，执行Callable任务后，可以获取一个Future的对象，在该对象上调用get就可以获取到Callable任务返回的Object了，在结合线程池接口ExecutorService就可以实现有返回结果的多线程。

如何遍历一个未知深度的树

先访问根结点，后选择一子结点访问并访问该节点的子结点，持续深入后再依序访问其他子树，通过递归实现。

void travel(treenode* nd){
for(treenode* nex :　nd->childs){
travel(nex);
}
return;
}

1.深度优先

是对每一个可能的分支路径深入到不能在深入为止，而且每个节点只能那个访问一次。对于图中例子来说深度优先遍历的结果就是：A,B,D,E,I,C,F,G,H (假设先走子节点的左侧)。深度优先遍历各个子节点，需要用到栈（Stack）这种数据结构。stack的特点是先进先出，整个遍历过程如下：

首先将A节点压入栈中，stack（A）
将A节点弹出，同时将A的子节点C，B压入栈中，此时B在栈的顶部，stack(B,C)
将B节点弹出，同时将B的子节点E，D压入栈中，此时D在栈的顶部，stack（D,E,C）
将D节点弹出，没有子节点压入,此时E在栈的顶部，stack（E，C）
将E节点弹出，同时将E的子节点I压入，stack（I,C）

.....依次往下，最终遍历完成，java代码如下：

public void depthFirst() {

Stack<Map<String, Object>> nodeStack = new Stack<Map<String, Object>>();

Map<String, Object> node = new HashMap<String, Object>();

nodeStack.add(node);

while (!nodeStack.isEmpty()) {

node = nodeStack.pop();

System.out.println(node);

//获得节点的子节点，对于二叉树就是获得节点的左子结点和右子节点

List<Map<String, Object>> children = getChildren(node);

if (children != null && !children.isEmpty()) {

for (Map child : children) {

nodeStack.push(child);

}

}

}

}
//节点使用Map存放

2.广度优先

其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。对于上面的例子来说，广度优先遍历的结果是：A,B,C,D,E,F,G,H,I(假设每层节点从左到右访问)。广度优先遍历各个节点，需要使用到队列（Queue）这种数据结构，queue的特点是先进先出，其实也可以使用双端队列，区别就是双端队列首尾都可以插入和弹出节点。整个遍历过程如下：

首先将A节点插入队列中，queue（A）
将A节点弹出，同时将A的子节点B，C插入队列中，此时B在队列首，C在队列尾部，queue（B，C）
将B节点弹出，同时将B的子节点D，E插入队列中，此时C在队列首，E在队列尾部，queue（C，D，E）
将C节点弹出，同时将C的子节点F，G，H插入队列中，此时D在队列首，H在队列尾部，queue（D，E，F，G，H）
将D节点弹出，D没有子节点，此时E在队列首，H在队列尾部，queue（E，F，G，H）

...依次往下，最终遍历完成，Java代码如下：

public void breadthFirst() {

Deque<Map<String, Object>> nodeDeque = new ArrayDeque<Map<String, Object>>();

Map<String, Object> node = new HashMap<String, Object>();

nodeDeque.add(node);

while (!nodeDeque.isEmpty()) {

node = nodeDeque.peekFirst();

System.out.println(node);

//获得节点的子节点，对于二叉树就是获得节点的左子结点和右子节点

List<Map<String, Object>> children = getChildren(node);

if (children != null && !children.isEmpty()) {

for (Map child : children) {

nodeDeque.add(child);

}

}

}

}

//这里使用的是双端队列，和使用queue是一样的

接口和抽象类有什么区别

共同点
是上层的抽象层。都不能被实例化。都能包含抽象的方法，这些抽象的方法用于描述类具备的功能，但是不比提供具体的实现。
区别
在抽象类中可以写非抽象的方法，从而避免在子类中重复书写他们，这样可以提高代码的复用性，这是抽象类的优势，接口中只能有抽象的方法。一个类只能继承一个直接父类，这个父类可以是具体的类也可是抽象类，但是一个类可以实现多个接口。

谈谈对单例的理解，以及实现方式

单例的特点

构造方法不对外开放,为private
确保单例类只有一个对象,尤其是多线程模式下
通过静态方法或枚举返回单例对象
确保单例类在反序列化是不会重新创建新的对象

实现方式主要有如下几种：

1、饿汉式

public class Singleton {
    /*
    * 饿汉式是在声明的时候就已经初始化Singleton1,确保了对象的唯一性
    *
    * 声明的时候就初始化对象会浪费不必要的资源
    * */
    private static Singleton instance = new Singleton();

    private Singleton() {
    }

    // 通过静态方法或枚举返回单例对象
    public Singleton getInstance() {
        return instance;
    }
}
2、懒汉式
public class Singleton {

    private static Singleton instance;

    private Singleton() {
    }

    /*
    * getInstance 添加了synchronized 关键字,,也就是说 getInstance 是一个同步方法,
    * 这就是懒汉式在多线程中保持唯一性的方式
    *
    * 懒汉式存在的问题是,即是instance已经被创建,每次调用getInstance方法还是会同步,这样就会浪费一些不必要的资源
    * */
    public static synchronized Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}
3、Double Check Lock(DCL模式)
class Singleton {
private static Singleton instance;

    private Singleton() {
    }

    /**
     * getInstance 进行了两次判空,第一次判空是为了不必要的同步,第二次判空为了在instance 为 null 的情况下创建实例
     * 既保证了线程安全且单例对象初始化后调用getInstance又不会进行同步锁判断
     * <p>
     * 优点:资源利用率高,效率高
     * 缺点:第一次加载稍慢,由于java处理器允许乱序执行,偶尔会失败
     *
     * @return
     */
    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (Singleton.class) {
                if (instance == null) {
                    instance = new Singleton3();
                }
            }
        }
        return instance;
    }
}
4、静态内部类实现单例模式
public class Singleton {
    /*
    *当第一次加载Singleton类时并不会初始化SINGLRTON,只有第一次调用getInstance方法的时候才会初始化SINGLETON
    *第一次调用getInstance 方法的时候虚拟机才会加载SingletonHoder类,这种方式不仅能够保证线程安全,也能够保证对象的唯一,
    *还延迟了单例的实例化,所有推荐使用这种方式
    * */
    private Singleton() {
    }

    public Singleton getInstance() {
        return SingletonHolder.SINGLETON;
    }

    private static class SingletonHolder {
        private static final Singleton SINGLETON = new Singleton();
    }
}5、枚举实现单例模式
public enum Singleton {
/**
*枚举是写法最简单的
* 默认枚举实例的创建时线程安全的,且在任何一种情况下它都是单例,包括反序列化
* */
INSTANCE;
}
6、使用容器实现单例
public class Singleton {
    /**
     * 将多种类型的单例放到统一的Map将集合中,根据相应的Key获取对应的对象
     *
     * 这种方式是我们可以管理多种类型的单例,可以使用统一接口进行获取操作
     * 降低了使用成本,也隐藏了具体实现,降低了耦合度
     */
    public static Map<String, Object> objMap = new HashMap<String, Object>();

    private Singleton() {
    }

    public static void registerInstance(String key, Object instance) {
        if (!objMap.containsKey(key)) {
            objMap.put(key, instance);
        }
    }

    public static Object getInstance(String key) {
        return objMap.get(key);
    }
}

结束语

如果你有好的答案可以提交至：

https://github.com/codeegginterviewgroup/CodeEggDailyInterview

往期文章：

今日问题：

大家觉得这个系列对你的帮助大吗？

快来码仔社群解锁新姿势吧！社群升级：Max你的学习效率

”FAN某”的离婚财产分割判决书（全文）

”FAN某”的离婚财产分割判决书（全文）

哈里斯女粉搞4B运动、毒杀丈夫，回旋镖能否让美国“血流成河”

比国产光刻机更重要的IPO要来了！

这把绝对高端局，只有中国人才懂